package com.jack.leetcode.eachproblem_2020;

import com.google.common.collect.Lists;

import java.util.*;

/**
 * Created by zhang_j on 2020/11/4
 */
public class 除法求值 {

    public static void main(String[] args) {
        List<List<String>> equations = new ArrayList<>();
        equations.add(Lists.newArrayList("a","c"));
        equations.add(Lists.newArrayList("b","e"));
        equations.add(Lists.newArrayList("c","d"));
        equations.add(Lists.newArrayList("e","d"));

        double[] values = {2.0,3.0,0.5,5.0};
        List<List<String>> queries = new ArrayList<>();
        queries.add(Lists.newArrayList("a","b"));
        calcEquation(equations, values, queries);
    }

    static double[][] g;
    static Map<String, Integer> map = new HashMap<>();
    static int n = 0;

    private static void floyd(){
        for(int i = 0;i < n;i++){
            for(int j = 0;j < n;j++){
                for(int k = 0;k < n;k++){
                    if(g[j][i] >= 0 && g[i][k] >= 0){
                        g[j][k] = g[j][i] * g[i][k];
                    }
                }
            }
        }
    }
    public static double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        for (List<String> equation : equations) {
            if(!map.containsKey(equation.get(0))){
                map.put(equation.get(0), n++);
            }
            if(!map.containsKey(equation.get(1))){
                map.put(equation.get(1), n++);
            }
        }
        g = new double[n][n];
        for(int i = 0;i < n;i++){
            Arrays.fill(g[i], -1);
        }
        for(int i = 0;i < n;i++){
            g[i][i] = 1.0;
        }
        int index = 0;
        for (List<String> equation : equations) {
            g[map.get(equation.get(0))][map.get(equation.get(1))] = values[index];
            g[map.get(equation.get(1))][map.get(equation.get(0))] = 1.0 / values[index++];
        }
        floyd();
        double[] result = new double[queries.size()];
        index = 0;
        for (List<String> query : queries) {
            String a = query.get(0), b = query.get(1);
            if(!map.containsKey(a) || !map.containsKey(b) || g[map.get(a)][map.get(b)] == -1){
                result[index++] = -1.0;
            }else{
                result[index++] = g[map.get(a)][map.get(b)];
            }
        }
        return result;
    }
}
